/*  --- 使用PriorityQueue ---

我们知道，Queue是一个先进先出（FIFO）的队列。

在银行柜台办业务时，我们假设只有一个柜台在办理业务，但是办理业务的人很多，怎么办？

可以每个人先取一个号，例如：A1、A2、A3……然后，按照号码顺序依次办理，实际上这就是一个Queue。

如果这时来了一个VIP客户，他的号码是V1，虽然当前排队的是A10、A11、A12……但是柜台下一个呼叫的客户号码却是V1。

这个时候，我们发现，要实现“VIP插队”的业务，用Queue就不行了，因为Queue会严格按FIFO的原则取出队首元素。我们需要的是优先队列：PriorityQueue。

PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。

要使用PriorityQueue，我们就必须给每个元素定义“优先级”。我们以实际代码为例，先看看PriorityQueue的行为：	*/
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
	public static void main(String[] args) {
		Queue<String> q = new PriorityQueue<>();

		//添加3个元素到队列
		q.offer("Apple");
		q.offer("Pear");
		q.offer("Banana");

		System.out.println(q.poll()); //Apple
		System.out.println(q.poll()); //Banana
		System.out.println(q.poll()); //Pear
		System.out.println(q.poll()); //null,因为Queue为空
	}
}


/*
我们放入的顺序是"apple"、"pear"、"banana"，但是取出的顺序却是"apple"、"banana"、"pear"，这是因为从字符串的排序看，"apple"排在最前面，"pear"排在最后面。

因此，放入PriorityQueue的元素，必须实现Comparable接口，PriorityQueue会根据元素的排序顺序决定出队的优先级。

如果我们要放入的元素并没有实现Comparable接口怎么办？PriorityQueue允许我们提供一个Comparator对象来判断两个元素的顺序。我们以银行排队业务为例，实现一个PriorityQueue：	*/
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
	public static void main(String[] args) {
		Queue<User> q = new PriorityQueue<>(new UserComparator());

		//添加3个元素Queue
		q.offer(new User("Bob","A1"));
		q.offer(new User("Alice", "A2"));
		q.offer(new User("Boss", "V1"));

		System.out.println(q.poll()); //Boss/V1
		System.out.println(q.poll()); //Bob/A1
		System.out.println(q.poll()); //Alice/A2
		System.out.println(q.poll()); //null,因为Queue为空
	}
}

class UserComparator implements Comparator<User> {
	public int compare(User u1, User u2) {
		if (u1.number.charAt(0) == u2.number.charAt(0)) {
			//如果两人的号都是A开头/都是V开头,比较号的大小
			// return u1.number.compareTo(u2.number);

			//方法1
			int num1 = Integer.parseInt(u1.number.substring(1, u1.number.length()));
			int num2 = Integer.parseInt(u2.number.substring(1, u2.number.length()));

			return Integer.compare(num1, num2);

			//方法2
			return u1.number.length() - u2.number.length() > 0 ? 1 : u1.number.compareTo(u2.number);

			//方法3(更好)
			return u1.number.length() == u2.number.length() ? u1.number.compareTo(u2.number) : Integer.compare(u1.number.length(), u2.number.length());
		}

		if (u1.number.charAt(0) == 'V') {
			//u1的号码是V开头,优先级高
			return -1;
		} else {
			return 1;
		}
	}

	@Override
	public int compareTo(User u) {

	}
}

class User {
	public final String name;
	public final String number;

	public User(String name, String number) {
		this.name = name;
		this.number = number;
	}

	public String toString() {
		return name + "/" + number ;
	}
}

/*
实现PriorityQueue的关键在于提供的UserComparator对象，它负责比较两个元素的大小（较小的在前）。UserComparator总是把V开头的号码优先返回，只有在开头相同的时候，才比较号码大小。

上面的UserComparator的比较逻辑其实还是有问题的，它会把A10排在A2的前面，请尝试修复该错误。

*/



/*  --- PriorityQueue の 小结 --- 

1. PriorityQueue实现了一个优先队列:从队首获取元素时,总是获取优先级最高的元素。

2. PriorityQueue默认按元素比较的顺序排序（必须实现Comparable接口），也可以通过Comparator自定义排序算法（元素就不必实现Comparable接口）。
































